package 强化训练;

import java.util.Scanner;
//已通过
public class day23字符串的编辑距离 {
    String s1;
    String s2;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
    }
    public static int minDist(String str1 ,String str2){
        //参加状态容器
        int len1 = str1.length();
        int len2 = str2.length();
        char[] wd1 = str1.toCharArray();
        char[] wd2 = str2.toCharArray();
        int[][] dp = new int[len1+1][len2+1];
        //初始化
        for (int i = 0; i < len1+1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i < len2+1; i++) {
            dp[0][i] = i;
        }

        //填表
        for (int i = 1; i < len1+1; i++) {
            for (int j = 1; j < len2+1; j++) {
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + 1;
                //dp[i-1][j]：删除第i个元素，和j相等,dp[i][j-1]，删除str2的第j个元素，和str1相等
                //替换
                if (wd1[i-1] == wd2[j-1]){//相等不替换，操作为0
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1]);
                    //dp[i-1][j-1]说明此时前i，j个元素已经编辑完成，当前位置不需要编辑，所以编辑次数为dp[i-1][j-1] + 0
                }else {
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1] + 1);
                    //不相等，则需要替换
                }
            }
        }
        return dp[len1][len2];
    }
}
